\documentclass[UTF8]{ctexart}

\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage{xcolor}
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage[colorlinks,linkcolor=red]{hyperref}

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage[linesnumbered,boxed,lined,ruled]{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\usepackage{listings}

\usepackage{graphicx}
\usepackage{float}
\title{LU分解程序说明文档}
\author{黎吉国&201618013229046}
\begin{document}
\maketitle
\newpage
\section{程序简介}
该程序由$matlab$实现，可以实现任意方阵的$LU$分解，分解形式为$PA=PLU$。当输入矩阵是奇异方阵时，会提示错误信息，输入不是方阵时，也会返回错误信息。源码在$git.oschaina$上开源\href{http://git.oschina.net/jiguo_li/assignment/tree/master/matrix/20161002?dir=1&filepath=matrix%2F20161002&oid=13121dbbe75754d7d47c5d7a709b9c86b0368ef3&sha=7ea70bc9791b3c48f4f310b11bd106816668253c}{@Jiguo\_Li}。
\section{算法原理}
算法基于部分主元的高斯消去法，使用行初等变换将矩阵$A$变换为一个行标准型，变换结果就是$U$矩阵，同时，初等变换的过程的逆矩阵是$L$矩阵，变换过程中的行交换的记录，是$P$矩阵。算法示例可以参考课件4.pdf的51页。
见图1。\\
\begin{figure}[H]
\centering
\includegraphics[width=6in,height=3.5in]{LU.jpg}
\caption{LU分解示例}
\label{fig:graph}
\end{figure}
\section{算法流程}
使用伪代码描述如下：
\begin{algorithm}
  \caption{方阵的LU分解}
      \KwData{a nonsingular square matrix A}
      \KwResult{result of LU factorization: L,U,P}
      \Begin{
        \tcp{init}
        $P$ \leftarrow \text{a uint square matrix as A};\\
        $L$ \leftarrow \text{a zero square matrix as A};\\
        $U$ \leftarrow \text{a zero square matrix as A};\\
        \tcp{check the input}
          \If{A is not square}
          {
            error(A should be a square matrix);\\
            \Return;
          }
          \If{det(A)=0}
          {
            error(A is nonsingular, no LU Factorization);\\
            \Return;
          }
          \For{$j$ \leftarrow $1$ \KwTo \text{the cloumn of A}-1}
          {
            $c$ \leftarrow \text{the jth cloumn of A};\\
            \tcp{find the pivot of each cloumn}
            [$povit\_value,povit\_row$] \leftarrow \text{the max abs value and its index of} $c$;\\
            \tcp{swap the povit to (j,j)}
            swap row($j$) and row($povit\_row$) for A;\\
            swap row($j$) and row($povit\_row$) for P;\\
            swap row($j$) and row($povit\_row$) for L;\\
            \tcp{elimate the element below the povit}
            \For{$k \leftarrow j+1$ \KwTo $\text{the row of A}$}
            {
              $scale \leftarrow A(k,j)/pivot$;\\
              $L(k,j)=scale$;\\
              $kth \text{row of A} \leftarrow kth \text{row of A} + jth \text{row of A}$;\\
            }
          }
          diag element of L $\leftarrow 1$;\\
          $U=A$;\\
          $P=P$;\\
      }
\end{algorithm}
\newpage
\section{如何使用}
在matlab中调用该程序的示例如下：(matlab的当前目录指向$LU\_factorization.m$所在文件夹)
\lstset{language=Matlab}%代码语言使用的是matlab
\lstset{breaklines}%自动将长的代码行换行排版
\lstset{extendedchars=false}%解决代码跨页时，章节标题，页眉等汉字不显示的问题
\begin{lstlisting}[frame=single]
>> test()
input:

A =

     1     4     5
     4    18    26
     3    16    30

output:

L =

    1.0000         0         0
    0.7500    1.0000         0
    0.2500   -0.2000    1.0000


U =

    4.0000   18.0000   26.0000
         0    2.5000   10.5000
         0         0    0.6000


P =

     0     1     0
     0     0     1
     1     0     0


>> help LU_factorization
  [L,U,P]=LU_factorization(A)
 A: a square matrix which is nonsingular
 L: the lower-triangular matrix of A
 U: the upper-triangular matrix of A
 P: the permutation matrix records the various interchanges used

>> A=[1,4,5;4,18,26;3,16,30];
>> [L,U,b]=LU_factorization(A)

L =

    1.0000         0         0
    0.7500    1.0000         0
    0.2500   -0.2000    1.0000


U =

    4.0000   18.0000   26.0000
         0    2.5000   10.5000
         0         0    0.6000


b =

     0     1     0
     0     0     1
     1     0     0
>> A=[1,4,5;4,18,26;3,16,30;1,1,1]

A =

    1     4     5
    4    18    26
    3    16    30
    1     1     1

>> [L,U,b]=LU_factorization(A)
Error using LU_factorization (line 16)
the matrix for LU Factorization should be square
>> A=[1,2,3;2,4,6;3,6,9]

A =

     1     2     3
     2     4     6
     3     6     9

>> [L,U,b]=LU_factorization(A)
Error using LU_factorization (line 20)
the matrix for LU Factorization should be nonsigular

\end{lstlisting}


\end{document}
